public class Hannota {

    //1   A->C      1
    //2   A->B     A->C    B->C    3
    //3   A->C     A->B    C->B    A->C   B->A   B->C    A->C   7     2^N - 1

    // n 个 盘子
    // n-1 个盘子 从pos1 借助 pos3 放到 pos2
    // 把pos1 放到 pos3
    // n-1 个盘子 从pos2 借助 pos1 挪到 pos3

    /**
     *
     * @param n
     * @param pos1  起始位置
     * @param pos2  中转位置
     * @param pos3  目的位置
     */
    public static void hanota(int n, char pos1, char pos2, char pos3){
        if (n == 1) {
            move(pos1,pos3);
            return;
        }
        hanota(n-1,pos1,pos3,pos2);
        move(pos1,pos3);
        hanota(n-1,pos2,pos1,pos3);
    }
    public static void move(char pos1,char pos2){
        System.out.print(pos1+"->"+pos2+" ");
    }

    public static void main(String[] args) {
        hanota(3,'A','B','C');
    }
}
